/**
 * @file mobjbuf.h
 *
 * @author yhuan416<yhuan416@foxmail.com>
 * @date 2025-8-14
 *
 * @brief 携带淘汰机制的内存池
 *          申请新空间时, 通过外部回调淘汰部分旧数据
 *
 * @date 2025-8-14
 *          初次提交
 */
#include "mobjbuf.h"

// 节点头部大小
#define mobjbuf_header_size sizeof(mobjbuf_header_t)

// 对齐上界
#define mobjbuf_align_up(size) (((size) + (MOBJBUF_ALIGN - 1)) & ~(MOBJBUF_ALIGN - 1))

// 当前obj是否空闲
#define mobjbuf_header_is_free(cur) ((cur) && (cur)->is_free)

// 两个obj是否连续
#define mobjbuf_header_is_next_obj(cur, next) ((uint8_t *)(cur) + (cur)->size == (uint8_t *)(next))

static bool is_valid_ptr(mobjbuf_t *objbuf, void *ptr)
{
    return ptr >= objbuf->buffer &&
           (char *)ptr < ((char *)objbuf->buffer + objbuf->buf_size);
}

/**
 * @brief 从链表中移除块
 *
 * @param list 链表结构指针
 * @param header 要移除的块头部指针
 */
static void remove_from_list(mobjbuf_list_t *list, mobjbuf_header_t *header)
{
    if (header->next == header)
    {
        list->list = NULL; // 链表空
        list->bytes = 0;
        list->count = 0;
    }
    else
    {
        header->prev->next = header->next;
        header->next->prev = header->prev;
        if (list->list == header)
        {
            list->list = header->next; // 更新链表头
        }

        list->count--;
        list->bytes -= header->size;
    }
}

/**
 * @brief 将块加入空闲链表（按地址排序）
 *
 * @param list 链表结构指针
 * @param header 空闲块头部指针
 */
static void add_to_free_list(mobjbuf_list_t *list, mobjbuf_header_t *header)
{
    mobjbuf_header_t *current, *start;

    if (list->list == NULL)
    {
        header->prev = header;
        header->next = header;
        list->list = header;

        list->count = 1;
        list->bytes = header->size;

        return;
    }

    // 查找插入位置（按地址升序）
    current = list->list;
    start = current;

    do
    {
        if ((uint8_t *)header < (uint8_t *)current)
        {
            break;
        }
        current = current->next;
    } while (current != start);

    // 插入到current之前
    header->prev = current->prev;
    header->next = current;
    current->prev->next = header;
    current->prev = header;

    // 更新链表头（若插入在头部）
    if (header < list->list)
    {
        list->list = header;
    }

    list->count++;
    list->bytes += header->size;
}

/**
 * @brief 加入已分配链表
 *
 * @param list 链表结构指针
 * @param header 已分配块头部指针
 */
static void add_to_alloc_list(mobjbuf_list_t *list, mobjbuf_header_t *header)
{
    if (list->list == NULL)
    {
        header->prev = header;
        header->next = header;
        list->list = header;
    }
    else
    {
        header->prev = list->list->prev;
        header->next = list->list;
        list->list->prev->next = header;
        list->list->prev = header;
    }

    list->count++;
    list->bytes += header->size;
}

/**
 * @brief 循环合并所有相邻空闲块
 *
 * @param list 链表结构指针
 */
static void merge_free_blocks(mobjbuf_list_t *list)
{
    mobjbuf_header_t *current, *begin, *next, *merge_start, *merge_end;
    size_t merged_size;
    bool found_merge;

    if (list->list == NULL)
    {
        return;
    }

    current = list->list;
    begin = current;

    do
    {
        // 如果当前块不是空闲块，跳过
        if (!current->is_free)
        {
            current = current->next;
            continue;
        }

        // 查找从current开始的连续相邻空闲块
        merge_start = current;
        merge_end = current;
        merged_size = current->size;
        found_merge = false;

        next = current->next;

        // 向后查找所有相邻的空闲块
        while (next != begin && mobjbuf_header_is_free(next) && mobjbuf_header_is_next_obj(merge_end, next))
        {
            merge_end = next;
            merged_size += next->size;
            next = next->next;
            found_merge = true;
        }

        if (found_merge)
        {
            // 有相邻块需要合并
            mobjbuf_header_t *temp = merge_start->next; // 从merge_start的下一个开始

            // 从链表中移除要合并的其他块（不包括merge_start）
            while (temp != next)
            {
                mobjbuf_header_t *to_remove = temp;
                temp = temp->next;
                remove_from_list(list, to_remove);
            }

            // 从链表中移除merge_start
            remove_from_list(list, merge_start);

            // 更新merge_start的大小
            merge_start->size = merged_size;

            // 重新追加到free_list中
            add_to_free_list(list, merge_start);

            // 从合并后的块继续遍历
            current = merge_start;
        }

        // 指向后续块
        current = current->next;

    } while (current != begin);
}

/**
 * @brief 查找满足大小的空闲块
 *
 * @param objbuf 内存池对象
 * @param size 需要的大小（包括头部）
 *
 * @return 找到的空闲块头部指针，未找到则返回NULL
 */
static mobjbuf_header_t *mobjbuf_find_free_block(mobjbuf_t *objbuf, size_t size)
{
    mobjbuf_header_t *current = objbuf->free_list.list;
    mobjbuf_header_t *start = current;

    if (current == NULL)
    {
        return NULL;
    }

    do
    {
        if (current->size >= size)
        {
            return current;
        }
        current = current->next;
    } while (current != start);

    return NULL;
}

// Init
int mobjbuf_init(mobjbuf_t *objbuf, void *buffer, size_t buf_size)
{
    mobjbuf_header_t *header = NULL;

    if (buf_size < mobjbuf_header_size + 8)
    {
        return -1; // 缓冲区过小
    }

    objbuf->buffer = buffer;
    objbuf->buf_size = buf_size;

    objbuf->free_list.list = NULL;
    objbuf->free_list.bytes = 0;
    objbuf->free_list.count = 0;

    objbuf->alloc_list.list = NULL;
    objbuf->alloc_list.bytes = 0;
    objbuf->alloc_list.count = 0;

    objbuf->min_block_size = mobjbuf_header_size + 8;

    // 初始化整个缓冲区为一个空闲块
    header = (mobjbuf_header_t *)buffer;
    header->prev = header;
    header->next = header;
    header->size = buf_size;
    header->is_free = true;

    add_to_free_list(&objbuf->free_list, header);
    return 0;
}

// Alloc
void *mobjbuf_alloc(mobjbuf_t *objbuf,
                    size_t size,
                    mobjbuf_discard_callback_fn discard_callback,
                    void *userdata)
{
    size_t required_size, allocated_size;
    mobjbuf_header_t *current = NULL, *new_free = NULL;

    if (objbuf == NULL || size == 0)
    {
        return NULL;
    }

    // 计算实际需要的大小（包括头部和对齐填充）
    required_size = mobjbuf_align_up((mobjbuf_header_size + size));

    // 查找空闲块（First-fit）
    if (NULL == (current = mobjbuf_find_free_block(objbuf, required_size)))
    {
        // try to discard
        if ((NULL != discard_callback) && (MOBJBUF_EVICT_DONE == discard_callback(objbuf, required_size, userdata)))
        {
            // 主动merge一次, 防止没有连续的大块
            merge_free_blocks(&objbuf->free_list);

            // 再次查找空闲块
            if (NULL == (current = mobjbuf_find_free_block(objbuf, required_size)))
            {
                return NULL; // 仍然没有找到合适的空闲块
            }
        }
        else
        {
            // 无法尝试释放内存
            return NULL;
        }
    }

    // 从空闲链表移除当前块
    remove_from_list(&objbuf->free_list, current);

    // 计算实际分配大小
    allocated_size = required_size;

    // 如果剩余空间足够，分割块
    if (current->size >= allocated_size + objbuf->min_block_size)
    {
        // 创建新空闲块（剩余部分）
        new_free = (mobjbuf_header_t *)((uint8_t *)current + allocated_size);
        new_free->size = current->size - allocated_size;
        new_free->is_free = true;

        // 原块更新为分配块
        current->size = allocated_size;

        // 新空闲块加入链表
        add_to_free_list(&objbuf->free_list, new_free);
        merge_free_blocks(&objbuf->free_list);
    }

    // 标记为已分配
    current->is_free = false;

    // 加入已分配链表
    add_to_alloc_list(&objbuf->alloc_list, current);

    // 返回用户数据区域的指针（在头部之后）
    return (void *)((uint8_t *)current + mobjbuf_header_size);
}

// free
void mobjbuf_free(mobjbuf_t *objbuf, void *ptr)
{
    // 释放内存
    mobjbuf_free_without_merge(objbuf, ptr);

    // 合并相邻空闲块
    merge_free_blocks(&objbuf->free_list);
}

/**
 * @brief 释放内存（不合并空闲块）
 *
 * @param objbuf 内存池对象
 * @param ptr 要释放的内存指针
 */
void mobjbuf_free_without_merge(mobjbuf_t *objbuf, void *ptr)
{
    mobjbuf_header_t *header = NULL;

    if (ptr == NULL || objbuf == NULL)
    {
        return;
    }

    // 检查指针是否在有效范围内
    if (!is_valid_ptr(objbuf, ptr))
    {
        return;
    }

    // 找到头部（用户数据指针减去头部大小）
    header = (mobjbuf_header_t *)((uint8_t *)ptr - mobjbuf_header_size);

    // 检查header是否在有效范围内
    if (!is_valid_ptr(objbuf, header) ||
        (char *)header + sizeof(mobjbuf_header_t) > (char *)objbuf->buffer + objbuf->buf_size)
    {
        return;
    }

    if (header->is_free)
    {
        return; // 已释放
    }

    // 从已分配链表移除
    remove_from_list(&objbuf->alloc_list, header);

    // 标记为空闲
    header->is_free = true;

    // 加入空闲链表
    add_to_free_list(&objbuf->free_list, header);
}

/**
 * @brief 合并所有空闲块
 *
 * @param objbuf 内存池对象
 */
void mobjbuf_merge_free_blocks(mobjbuf_t *objbuf)
{
    // 合并相邻空闲块
    merge_free_blocks(&objbuf->free_list);
}

void mobjbuf_dump(mobjbuf_t *objbuf)
{
    mobjbuf_header_t *current, *start;
    size_t alloc_count = 0, free_count = 0, alloc_bytes = 0, free_bytes = 0;

    if (NULL == objbuf)
    {
        printf("[mobjbuf_dump] objbuf is NULL!\n");
        return;
    }

    printf("\n================= mobjbuf status =================\n");
    printf("mobjbuf info:\n");
    printf("  ptr: %p\n", objbuf);
    printf("  buffer: %p\n", objbuf->buffer);
    printf("  buf_size: %zu\n", objbuf->buf_size);
    printf("  min_block_size: %zu\n", objbuf->min_block_size);
    printf("  alloc_list: %p\n", objbuf->alloc_list.list);
    printf("  free_list:  %p\n", objbuf->free_list.list);
    printf("------------------------------------------------\n");

    // 打印已分配块
    printf("[alloc block]:\n");
    if (objbuf->alloc_list.list)
    {
        current = objbuf->alloc_list.list;
        start = current;
        do
        {
            printf("  #%zu: " mobjbuf_header_format_s "\n", alloc_count, mobjbuf_header_format(current));
            alloc_bytes += current->size;
            alloc_count++;
            current = current->next;
        } while (current != start);
    }
    else
    {
        printf("  (NONE)\n");
    }
    printf("  Total: %zu block, %zu bytes\n", objbuf->alloc_list.count, objbuf->alloc_list.bytes);
    printf("------------------------------------------------\n");

    // 打印空闲块
    printf("[free block]:\n");
    if (objbuf->free_list.list)
    {
        current = objbuf->free_list.list;
        start = current;
        do
        {
            printf("  #%zu: " mobjbuf_header_format_s "\n", free_count, mobjbuf_header_format(current));
            free_bytes += current->size;
            free_count++;
            current = current->next;
        } while (current != start);
    }
    else
    {
        printf("  (NONE)\n");
    }
    printf("  Total: %zu block, %zu bytes\n", objbuf->free_list.count, objbuf->free_list.bytes);
    printf("------------------------------------------------\n");

    printf("[statistics]:\n");
    printf("  Total memory: %zu bytes\n", objbuf->buf_size);
    printf("  Allocated: %zu bytes, blocks: %zu\n", objbuf->alloc_list.bytes, objbuf->alloc_list.count);
    printf("  Free:   %zu bytes, blocks: %zu\n", objbuf->free_list.bytes, objbuf->free_list.count);
    printf("  Usage: %.2f%%\n", objbuf->buf_size ? (100.0 * objbuf->alloc_list.bytes / objbuf->buf_size) : 0.0);
    printf("================================================\n\n");
}
